1. Field of the Invention
The present invention relates generally to the field of cryptosystems, more particularly to a Montgomery modular multiplier for such cryptosystems.
2. Description of the Related Art
In information communication environments exchanging various data by way of computer networks, wired and/or mobile (wireless) communication fields, cryptographic systems (cryptosystems) are increasingly regarded as necessary facilities for assuring data security. Especially, it is necessary for an electronic accounting or identification system to be equipped with data security by employing encryption and/or decryption technologies. Cryptographic technologies may be briefly classified into the forms of a secret key (symmetric key, private key, or common key) and a public key (asymmetric key).
The Data Encryption System (DES) cryptographic algorithm proposed by the Department of Commerce of U.S.A. is one typical secret key type of cryptosystem. Other typical cryptosystems include the Government Standard (GOST) of ex-U.S.S.R, and the Internal Data Encryption Algorithm (IDEA) of Switzerland. For a secret key cryptosystem, it is advantageous to have an additional channel for security, since the partners exchanging information have to share the same secret key. Such secret key-type cryptosystems thus typically require maintenance and management of many secret keys by one user, in order for the user to communicate information with many other users.
A public key type of cryptosystem uses cryptographic and decryption keys different from each other, which may make it difficult to detect a corresponding key by the user, even though the person knows one of the two keys. In the public cryptosystem, information is scrambled or descrambled by means of a secret key and/or a public key (i.e., information may be scrambled using a private key and descrambled using a public key, and vice versa). While the public cryptosystem may be convenient in key management, because there is no need of an additional channel for sharing keys, and may provide improved data security as compared to a secret cryptosystem, a public cryptosystem is regarded as having a limited capacity to process high speed data, since two different keys must be generated, and because complex mathematical operations need to be performed for restoring information using the two different keys.
An advanced cryptographic system employs a Montgomery algorithm, which may be more advantageous for implementing a public key cryptographic algorithm in both hardware and software system embodiments. A cryptosystem using a Montgomery algorithm is able to transform a modular operation for a number, that is difficult to implement by hardware, into a shift operation of simplified multiplication and addition. The Montgomery algorithm uses an operand transformation process before and after a single multiplication operating step. Therefore, although a Montgomery-based cryptosystem may be slower than other modular multiplication systems in a single multiplication field, for applications running iterant multiplying operations, a Montgomery-based cryptosystem is able to process cryptographic operations faster than conventional public key based cryptographic algorithms because there is no need of an operand transformation step every processing cycle.
One of methods for enhancing processing speed for multiplication is to extend the number of radixes. If a radix value increases, the iterant number of accumulations in a given multiplication process decreases by a corresponding amount. However, increase of the radix number may cause a more complicated accumulation cycle due to additional processing steps, thus lengthening the processing time. For example, while it is relatively straightforward for a radix-2 operation algorithm to be implemented by hardware, the iterant number of accumulation cycles is double that of a radix-4 operation algorithm. Conversely, the radix-4 operation algorithm requires longer processing time for each iterant cycle and requires a more complex hardware architecture, relative to the hardware requirements for the radix-2 operation algorithm.